package com.github.yangyishe.p100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 57. 插入区间
 * https://leetcode.cn/problems/insert-interval/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
 *
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 * 输出：[[1,5],[6,9]]
 * 示例 2：
 *
 * 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 * 输出：[[1,2],[3,10],[12,16]]
 * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 * 示例 3：
 *
 * 输入：intervals = [], newInterval = [5,7]
 * 输出：[[5,7]]
 * 示例 4：
 *
 * 输入：intervals = [[1,5]], newInterval = [2,3]
 * 输出：[[1,5]]
 * 示例 5：
 *
 * 输入：intervals = [[1,5]], newInterval = [2,7]
 * 输出：[[1,7]]
 *
 *
 * 提示：
 *
 * 0 <= intervals.length <= 104
 * intervals[i].length == 2
 * 0 <= intervals[i][0] <= intervals[i][1] <= 105
 * intervals 根据 intervals[i][0] 按 升序 排列
 * newInterval.length == 2
 * 0 <= newInterval[0] <= newInterval[1] <= 105
 */
public class Problem57 {
    public static void main(String[] args) {
        int[][] intervals=new int[][]{
                {1,5},
//                {3,5},
//                {6,7},
//                {8,10},
//                {12,16},
        };
        int[] newInterval=new int[]{5,7};

        Problem57 problem57 = new Problem57();
        int[][] result = problem57.insert(intervals, newInterval);
        for (int[] ints : result) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * 思路(20231211):
     * 本次思路, 先不考虑怎么做效率最高, 先考虑实现出来
     * 1. 分别找到, 待插入区间的开始点和结束点, 位于哪个区间内, 或位于哪两个区间之间.
     *  -> 应该能获得两个下标+范围flag. 下标表示搜索点位于哪个下标对应的区间, 范围flag表示是在对应的开始点之后(表示位于区间内), 还是结束点之后(表示位于区间外)
     *  -> 方式使用轮次遍历, 直到找到结果. 时间复杂度为O(n)
     * 2. 确定位置之后, 基本就可确定如何替代区间了.
     *  -> 如果是开始点, 且在区间内, 则开始点被融入此前区间; 否则必然是新创建区间;
     *  -> 如果是结束点, 不论是否在区间内, 此前区间都被融入汇总区间;
     *
     *  边界值的处理情况:
     *  1. 如果是固有区间开始值, 与某个开始点或结束点相等, 则计入内部;
     *  2. 如果是固有区间结束值, 与某个开始点或结束点相等, 则计入内部;
     *
     * @param intervals
     * @param newInterval
     * @return
     */
    public int[][] insert(int[][] intervals, int[] newInterval){
        // 找区间的点位置(开始假定待插入区间在第一个区间外面)
        int startIndex=-1;
        boolean startInner=false;
        int endIndex=-1;
        boolean endInner=false;
        for(int i=0;i<intervals.length;i++){
            int[] interval=intervals[i];
            if(interval[0]>newInterval[0]){
                break;
            }
            startIndex++;
            if(interval[1]>=newInterval[0]){
                startInner=true;
                break;
            }
        }
        endIndex= startIndex==-1?-1:startIndex-1;
        for(int i=Math.max(startIndex,0);i<intervals.length;i++){
            int[] interval=intervals[i];
            if(interval[0]>newInterval[1]){
                break;
            }
            endIndex++;
            if(interval[1]>=newInterval[1]){
                endInner=true;
                break;
            }
        }

        // 合并
        List<int[]> resultList=new ArrayList<>();
        for(int i=0;i<=startIndex;i++){
            resultList.add(intervals[i]);
        }
        if(!startInner){
            resultList.add(newInterval);
        }
        int[] temp=resultList.get(resultList.size()-1);
        if(endInner){
           temp[1]=intervals[endIndex][1];
        }else{
            temp[1]=newInterval[1];
        }
        for(int i=endIndex+1;i<intervals.length;i++){
            resultList.add(intervals[i]);
        }

        return resultList.toArray(new int[resultList.size()][]);
    }

    /**
     * 思路:
     * 1. 仅对比区间开始时间点, 可用二分查找法, 但为了减少逻辑复杂度采用遍历查找, 获取比新区间的开始点小的最大区间, 如是第n个
     * 2. 对比新区间的开始点和第n个区间的结束点,
     *  如果开始点小于等于结束点, 则说明可以合并, 获取新的区间. 这之后再遍历以后的区间, 根据p56的情况遍历, 直到不能合并为止. 构建出新的结果集
     *  如果开始点大于结束点, 则新区间的开始点, 必然可以构建出一个新区间, 之后又是合并判断的事
     *  其他情况是处于二者之间, 则直接作为一个新的独立区间增加即可
     *
     *  为了让逻辑处理简单, 使用List来出来合并的事情
     *
     * @param intervals
     * @param newInterval
     * @return
     */
    public int[][] insert2(int[][] intervals, int[] newInterval) {
        if(intervals.length==0){
            return new int[][]{
                    newInterval
            };
        }
        // 二分查找匹配条件的开始点最大点
        int left = maxMinIndex(intervals, newInterval);


        List<int[]> resultList=new ArrayList<>();
        for(int i=0;i<=left;i++){
            resultList.add(intervals[i]);
        }

        if(left>=0&&newInterval[0]<=intervals[left][1]){
            int[] leftInterval = intervals[left];
            leftInterval[1]=Math.max(newInterval[1],leftInterval[1]);
            boolean judgeMerge=true;
            for(int i=left+1;i<intervals.length;i++){
                if(judgeMerge&&leftInterval[1]>=intervals[i][0]){
                    leftInterval[1]=Math.max(leftInterval[1],intervals[i][1]);
                }else{
                    judgeMerge=false;
                    resultList.add(intervals[i]);
                }
            }
            // while循环中, 应尽可能减少变量变化的设置
//            while((++left)<intervals.length&&leftInterval[1]>=intervals[left][0]){
//                leftInterval[1]=Math.max(leftInterval[1],intervals[left][1]);
//            }
//            while((++left)<intervals.length){
//                resultList.add(intervals[left]);
//            }
        }else if(left+1<intervals.length&&newInterval[1]>=intervals[left+1][0]){
            resultList.add(newInterval);
            newInterval[1]=Math.max(newInterval[1],intervals[left+1][0]);
            boolean judgeMerge=true;
            for(int i=left+2;i<intervals.length;i++){
                if(judgeMerge&&newInterval[1]>=intervals[i][0]){
                    newInterval[1]=Math.max(newInterval[1],intervals[i][1]);
                }else{
                    judgeMerge=false;
                    resultList.add(intervals[i]);
                }
            }

        }else{
            resultList.add(newInterval);
            for(int i=left+1;i<intervals.length;i++){
                resultList.add(intervals[i]);
            }
        }

        return resultList.toArray(new int[resultList.size()][]);
    }

    /**
     * 此处的二分查找, 只是为了锻炼脑力. 实际没有必要
     * @param intervals
     * @param newInterval
     * @return
     */
    public int maxMinIndex(int[][] intervals,int[] newInterval){
        if (intervals[0][0]>newInterval[0]) {
            return -1;
        }
        if(intervals[intervals.length-1][0]<newInterval[0]){
            return intervals.length-1;
        }
        int left=0;
        int right=intervals.length-1;
        while(left+1<right){
            int mid=(left+right)/2;
            if(newInterval[0]>=intervals[mid][0]&&newInterval[0]<intervals[mid+1][0]){
                return mid;
            }
            if(newInterval[0]<intervals[mid][0]){
                right=mid;
            }else{
                // newInterval[0]>=intervals[mid+1][0]
                left=mid+1;
            }
        }
        return left;
    }
}
